package Alibaba;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.StringJoiner;

/**
 * @author zhangmin
 * @create 2022-01-27 11:51
 * 93. 复原 IP 地址
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
 * 你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 * 1、回溯：路径：已经划分好的数字
 *         选择列表：选择在当前位置是与前一位组合为一个数字，还是单独成为一个数字
 *         终止条件：字符串到最后一位
 */
public class restoreIpAddresses93 {
    List<String> res;
    void backtrack(String s, int index, LinkedList<Integer> path,boolean canwith){
        if (index==s.length()){
            if (path.size()==4){
                //整个字符串完整转换
                StringBuffer sb=new StringBuffer();
                for (Integer i:path) {
                    sb.append(i).append('.');
                }
                String str=sb.toString();
                res.add(str.substring(0,str.length()-1));
            }
            return;
        }
        int last = Integer.parseInt(String.valueOf(s.charAt(index)));
        if (canwith){
            //可以与前一位合并，意味着path中已经有元素，且path中的最后一位不为0
            int lastInt=path.getLast();
            int cur=lastInt*10+last;
            if (cur<=255){
                //可以选择合并为同一个数字
                path.removeLast();
                path.addLast(cur);
                backtrack(s,index+1,path,true);
                path.removeLast();
                path.addLast(lastInt);
            }
        }
        //也可以选择不与前一位合并
        //不可与前一位合并,则单独成为一个数字，需要判断当前是否为0 ，为0时，下一次不可与之合并
        if(last==0){
            path.addLast(0);
            backtrack(s,index+1,path,false);
            path.removeLast();
        }else {
            //选择单独成为一个数字
            path.addLast(last);
            backtrack(s,index+1,path,true);
            path.removeLast();
        }
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length()<4){
            return new LinkedList<>();
        }
        res=new LinkedList<>();
        backtrack(s,0,new LinkedList<>(),false);
        return res;
    }

}
